import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

public class answer {
    //判断是否为回文字符串
    public boolean judge(String str) {
        char[] arr = str.toCharArray();
        int left = 0;
        int right = arr.length - 1;
        while (left != right) {
            if (arr[left] != arr[right]) {
                return false;
            }
        }
        return true;
    }

    //求平方根：将求平方根转化为二分查找
    public int mysqrt (int x) {
        if(x==1 ){
            return 1;
        }
        int left = 1;
        int right = x;
        while(left <= right){
            int mid = (left + right)/2;
            if(mid <= x/mid && (mid+1) > x/(mid+1) ){//使用除法防止越界
                return mid;
            }
            if(mid  > x/mid){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return 0;
    }

    //有效三角形个数
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);//O(nlogn)
        int sum = 0;
        //第一层循环固定一个数(O(N^2))
        for(int i = nums.length - 1;i >= 2 ;i--){
            int right = i - 1;
            int left = 0;
            while(left < right){
                if(nums[left] + nums[right] > nums[i]){
                    sum += (right - left);
                    right--;
                }else{
                    left++;
                }
            }
        }
        return sum;
    }

    //总价格为目标值的商品
    public int[] twoSum(int[] price, int target) {
        int left = 0;
        int right = price.length - 1;
        while(left < right){
            if(price[left] + price[right] > target){
                right--;
            }else if(price[left] + price[right] < target){
                left++;
            }else{
                return new int[]{price[left],price[right]};
            }
        }

        return new int[0];
    }

    //三数之和
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> List = new ArrayList<>();

        Arrays.sort(nums);

        for(int i =0 ;i<nums.length;){
            if(nums[i] > 0){
                break;
            }
            int left = i + 1;
            int right = nums.length - 1;
            while(left < right){
                if(nums[left] + nums[right] > nums[i]*-1){
                    right--;
                }else if(nums[left] + nums[right] < nums[i]*-1){
                    left++;
                }else{
                    List<Integer> ret = new ArrayList<>();
                    ret.add(nums[i]);
                    ret.add(nums[left]);
                    ret.add(nums[right]);
                    List.add(ret);
                    left++;
                    right--;
                    while(left < right && nums[left - 1]  == nums[left]){
                        left++;

                    }

                    while(left < right && nums[right + 1] == nums[right]){
                        right--;
                    }
                }
            }
            i++;
            while(i<nums.length && nums[i-1] == nums[i]){
                i++;
            }
        }

        return List;
    }

    //四数之和
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;
        for(int i=0;i<n;){
            for(int j=i+1;j<n;){
                int left = j+1;
                int right = n-1;
                long aim = (long)target - nums[i] - nums[j];
                while(left < right){
                    if(nums[left] + nums[right] > aim){
                        right--;
                    }else if(nums[left] + nums[right] < aim){
                        left++;
                    }else{
                        ret.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                        left++;
                        right--;
                        while(left < right && nums[left-1] == nums[left]){
                            left++;
                        }
                        while(left < right && nums[right+1] == nums[right]){
                            right--;
                        }
                    }
                }
                j++;
                while(j<n && nums[j-1] == nums[j]){
                    j++;
                }
            }
            i++;
            while(i<n && nums[i-1] ==nums[i]){
                i++;
            }
        }

        return ret;
    }

    public static void main(String[] args) {
        int[] nums = {-1,0,1,2,-1,-4};
        List<List<Integer>> list = threeSum(nums);
        System.out.println(list);



    }

}
